package ch16;

/**
 * Created by zhangyunqi on 2017/10/22.
 */
import ch15.LinkedQueue;
import ch16.exceptions.ElementNotFoundException;
import ch16.exceptions.EmptyCollectionException;

import java.util.Iterator;
public abstract class LinkedBinaryTree<T> implements BinaryTree<T> {
    protected BTNode <T> root;

    public LinkedBinaryTree() {
        root = null;
    }

    public LinkedBinaryTree(T element) {
        root = new BTNode <T> ( element );
    }

    public LinkedBinaryTree(T element, LinkedBinaryTree <T> left,
                            LinkedBinaryTree <T> right) {
        root = new BTNode <T> ( element );
        root.setLeft ( left.root );
        root.setRight ( right.root );
    }


    public T getRootElement() {
        if (root == null)
            throw new EmptyCollectionException ( "Get root operation "
                    + "failed. The tree is empty." );

        return root.getElement ();
    }


    public LinkedBinaryTree <T> getLeft() {
        if (root == null)
            throw new EmptyCollectionException ( "Get left operation "
                    + "failed. The tree is empty." );

        LinkedBinaryTree <T> result = new LinkedBinaryTree <T> () {
            @Override
            public LinkedBinaryTree <T> getRight() {
                return null;
            }

            @Override
            public boolean contains(T target) {
                return false;
            }

            @Override
            public boolean isEmpty() {
                return false;
            }

            @Override
            public Iterable <T> preorder(BTNode <T> right) {
                return null;
            }

            @Override
            public Iterable <T> postorder() {
                return null;
            }
        };
        result.root = root.getLeft ();

        return result;
    }

    public T find(T target) {
        BTNode <T> node = null;

        if (root != null)
            node = root.find ( target );

        if (node == null)
            throw new ElementNotFoundException ( "Find operation failed. "
                    + "No such element in tree." );

        return node.getElement ();
    }

    public int size() {
        int result = 0;

        if (root != null)
            result = root.count ();

        return result;
    }

    public Iterable <T> inorder() {
        ArrayIterator <T> iter = new ArrayIterator <T> ();

        if (root != null)
            root.inorder ( iter );

        return (Iterable <T>) iter;
    }

    public Iterable <T> levelorder() {
        LinkedQueue <BTNode <T>> queue = new LinkedQueue <BTNode <T>> ();
        ArrayIterator <T> iter = new ArrayIterator <T> ();

        if (root != null) {
            queue.enqueue ( root );
            while (!queue.isEmpty ()) {
                BTNode <T> current = queue.dequeue ();

                queue.add ( current.getElement () );

                if (current.getLeft () != null)
                    queue.enqueue ( current.getLeft () );
                if (current.getRight () != null)
                    queue.enqueue ( current.getRight () );
            }
        }

        return (Iterable <T>) iter;
    }

    public Iterator <T> iterator() {
        return (Iterator <T>) inorder ();
    }

    public LinkedBinaryTree <T> getRight() {
        if (root == null) {
            throw new EmptyCollectionException ( "Get root operation" + "failed.The tree is empty." );
        }
        LinkedBinaryTree <T> result = new LinkedBinaryTree <T> () {
            @Override
            public LinkedBinaryTree <T> getLeft() {
                return null;
            }

            @Override
            public boolean contains(T target) {
                return true;
            }

            @Override
            public boolean isEmpty() {
                return true;
            }

            @Override
            public Iterable <T> preorder(BTNode <T> right) {
                return null;
            }

            @Override
            public Iterable <T> postorder() {
                return null;
            }

            @Override
            public Iterator <T> postorder(BTNode <T> ri) {
                return null;
            }
        };
        result.root = root.getRight ();
        return result;
    }

    public Iterable <T> preorder(BTNode <T> right) {
        if (root != null) {
            System.out.print ( root.count () + "  " );
            preorder ( root.getLeft () );
            preorder ( root.getRight () );
        }
        return null;
    }

    public Iterator <T> postorder(BTNode <T> ri) {
        if (root != null) {
            preorder ( root.getLeft () );
            preorder ( root.getRight () );
            System.out.print ( root.count () + "  " );
        }
        return null;
    }
}


